package com.mj.listen3.链表;

/**
 * https://leetcode-cn.com/problems/reverse-linked-list-ii/
 */
public class _92_反转链表部分链表 {
    public ListNode reverseBetween(ListNode head, int left, int right) {
        if (left > right) return head;
        // 链表的长度
        int len = 0;
        // left的前一个节点
        ListNode leftPre = null;
        // right的后一个节点
        ListNode rightLast = null;

        ListNode cur = head;
        while (cur != null) {
            len++;
            // 找前一个节点就是 len == left - 1
            leftPre = len == left - 1 ? cur : leftPre;
            // 找后一个节点就是 len == right + 1
            rightLast = len == right + 1 ? cur : rightLast;
            cur = cur.next;
        }
        // 符合条件：1 <= left <= right;  其它不符合条件直接返回head
        if (left < 1 || right > len) return head;

        // 开始反转
        ListNode node2 = leftPre == null ? head : leftPre.next;
        cur = node2.next;
        // 连接到右边不被反转的节点去
        node2.next = rightLast;

        // 开始反转
        while (cur != rightLast) {
            ListNode temp = cur.next;
            // 往前指
            cur.next = node2;
            node2 = cur;
            cur = temp;
        }

        // 反转完了，看一下leftLeft是否为空
        // 如果不为空，则返回原来的头；如果为空就直接返回最新的头
        if (leftPre != null) {
            leftPre.next = node2;
            return head;
        } else {
            // node2是反转之后的最后一个节点，就是最后会成为新的头节点
            return node2;
        }
    }
}
